How does an airport manages multiple flights?
The continuous growth of the air transportation industry has placed an enormous strain on the aviation system’s infrastructure. Congestion is persistent and arises on an almost daily basis as a consequence of even minor weather disturbances that cause reductions in nominal capacities. The Air Transport Association (2009) has estimated that delays increased direct operating costs to U.S. airlines by about $12 billion in 2007 and $9.5 billion in 2008. European airlines have cited figures in the $5 billion range for their costs. Air traffic flow management (ATFM) is playing a central role in alleviating these costs—a role that may become truly critical in the near future. ATFM attempts to prevent local demand-capacity imbalances by adjusting the flows of aircraft on a national or regional basis. 'Short Answer' In 2007, approximately 26% of all flights in the United States were delayed on arrival by more than 15 minutes, whereas another 3% were cancelled (U.S. Dept. of Transportation, 2007). Until recently, ATFM in the United States has been focused mainly on airport congestion. In this respect, the most popular flow management approach, by far, has been the assignment of “ground-holding” delays to departing flights, i.e., postponing departure time in order to absorb most delay on the ground instead of in the air. Beginning with a paper by Odoni (1987), who was the first to formulate the problem in mathematical terms, several models and algorithms have been proposed for computing optimal ground-holding strategies. Bertsimas and Odoni (1997) and, especially, Ball et al. (2007) and Hoffman et al. (2011) provide detailed relevant surveys. Very significant delays and system throughput degradations have increasingly also arisen as a result of enroute airspace problems and limitations. Especially during summer months, there are several key enroute sectors, both in the United States and in Europe, that are often operated at their full capacity and act as local bottlenecks. Traffic congestion at these sectors is as critical an issue as congestion in terminal airspace around major airports. Although the capacity of these enroute sectors has generally increased in recent years as a consequence of measures taken on a local and continent-wide basis (e.g., increasing the number of high-altitude flight levels), the problem posed by the enroute sector capacity constraints is persistent and may take at least one more decade to resolve (EUROCONTROL Performance Review Commission 2004). One of the implications of the simultaneous presence of airport and enroute airspace constraints is that devising good ATFM strategies has become a much more complicated task. Any mathematical model developed for this purpose has to consider a true network of capacitated elements, enroute sectors, and airports. Moreover, a larger set of options to resolve congestion must be considered simultaneously, including ground holding, airborne holding, flight rerouting, and speed control. For instance, an aircraft could be rerouted instead of being held on the ground, to reach its destination through a different flight path if its original route traversed a region that should be avoided for some reason, usually related to poor weather conditions and resulting sector congestion. In contrast to the case in which solely airport congestion is considered, the research literature dealing simultaneously with airport and enroute congestion is quite sparse. One of the first attempts to include enroute capacity restrictions in the ATFM problem was by Helme (1992), who proposed a multicommodity minimum-cost flow on a time-space network to assign airborne and ground delay to aggregate flows of flights. Although the formulation of this model is straightforward and easy to understand, its computational performance was weak. Lindsay et al. (1993) formulated a disaggregate deterministic 0-1 integer programming model for assigning ground and airborne holding to individual flights in the presence of both airport and airspace capacity constraints. Their proposed Time Assignment Model (TAM) determines the optimal temporal and spatial location of each aircraft, given a set of capacity constraints imposed by National Airspace System (NAS) resources. Bertsimas and Stock Patterson (1998) presented a deterministic 0-1 IP model to solve a similar problem. For each aircraft, a predetermined set of enroute sectors is specified as the route between its origin and destination. The model then determines the optimal departure time and sector occupancy time for each aircraft. The authors analyzed the polyhedral structure of the underlying linear relaxation and showed that several of the constraints provide facets of the convex hull of solutions. As a result, the proposed model enables very efficient computation of optimal solutions. Long Answer Lulli and Odoni (2007) presented a more macroscopic ATFM model of a network of capacitated enroute sectors and airports that illustrates the complexity, and occasionally counterintuitive characteristics, of optimal ATFM strategies in such environments. However, none of the models cited considers rerouting or speed control as options. They all assume that the flight path is known in advance and is fixed. To the best of our knowledge, the only paper that considers rerouting, at least at a macroscopic level, is the one by Bertsimas and Stock Paterson (2000), which describes a dynamic, multi-commodity, integer network-flow model. This model addresses routing as well as scheduling decisions. Aggregate flows are generated using a Lagrangian relaxation approach. A randomized rounding heuristic is then applied to decompose the aggregate flows into a collection of individual flight paths Finally, an integer packing problem is solved to obtain feasible and near-optimal individual flight routes. However, the computational performance of this model was not adequate for addressing problems encountered in realistic, very large-scale instances. These systems involve tens of possibly congested airports, more than 100 enroute sectors, and several thousand flights at a time. The proposed model combines the flexibility, in terms of the range of available ATFM options provided by the model of Bertsimas and Stock Paterson (2000) with the powerful mathematical properties of the model in Bertsimas and Stock Patterson (1998), to solve efficiently such very large-sized problems. The available options include rerouting, as well as ground holding, airborne holding, and speed control. The model optimizes for each flight the time of departure, the route selected, the time required to traverse each sector, and the time of arrival at the destination airport, taking into account the capacity of all the elements of the air traffic management system. Thus, the model determines how to control a flight throughout its duration, not simply before its departure. A main innovative feature of the model is the formulation of rerouting decisions in a very compact way. With respect to the model in Bertsimas and Stock Patterson (1998), our approach does not require any additional variables but only introduces some new constraints. These constraints force local routing conditions sufficient to perform the rerouting function efficiently. Three classes of valid inequalities that strengthen the polyhedral structure of the underlying relaxation are also introduced and play a critical role in improving the model’s computational performance. At a more microscopic level, Sherali et al. (2003) and Sherali et al. (2006) have developed the Airspace Planning and Collaborative Decision-Making Model (APCDM) to select a set of flight plans from a large set of alternatives for a set of aircraft in an airspace region, subject to flight safety, air traffic control, and airline equity considerations. The Mathematical Model This section presents a new modeling approach to handle ATFM with both airport and sector capacity restrictions. The mathematical model determines how to adjust the release time of each flight into the system (time of departure), how to control its flight speed once in the air, and how to reroute it in the presence of congestion in the enroute sectors along the preferred path. It considers efficiently all the combinations of possible actions that can be undertaken by air traffic managers, i.e., ground holding, airborne holding, miles-in-trail, and rerouting decisions. The airspace is divided into sectors. Each flight passes through contiguous sectors while en route to its destination. Therefore, an origin-to-destination route is represented as a sequence of sectors to be flown by an aircraft. In ATFM models that do not include rerouting as an option, the sequence of sectors to be flown is predetermined. To include rerouting into the set of options considered by the mathematical model, the set of sectors through which each aircraft might potentially fly has to be enlarged. The number of airplanes that may fly within a sector at any given time is limited. The limit is determined primarily by the number of aircraft that an air traffic controller can oversee simultaneously and may vary with the geographic location of the sector, its geometric configuration, and the weather conditions. We shall refer to the limits on the number of aircraft in any given sector at any given time as the enroute sector capacities. A key aspect of the proposed model is the definition of routes. The origin-destination routes—for any specific o-d ''pair—can be represented by digraphs. To ensure that each flight follows exactly one route, we use a set of local conditions based on the precedence relations among sectors. These conditions are analogous to the mass balance constraints in network flow problems, and they can be simply stated as follows to fly through a sector, any aircraft has to fly first through one of the preceding sectors for a number of time periods equal to at least the minimum flight time needed to traverse that preceding sector, or equivalent if an aircraft has flown a sector for at least the number of time periods needed to traverse it, then it may fly next through one of that sector’s subsequent sectors. The objective of the mathematical model is to design ATFM strategies that alleviate airspace and airport congestion maintaining smooth and economic flows of traffic consistent with capacity and workload constraints. In any specific instance of the problem, one may have to comply with capacity constraints at any or all the elements of the network under consideration, i.e., the sectors and the airports. '''The Decision Variables' The model of Bertsimas and Stock Patterson (1998) provided the starting point for the model presented herein. We used the same decision variables as that model: Notation: '''The model’s formulation requires definition of the following notation: The variables are defined only for the set of sectors an aircraft may fly through on its route to the destination airports. In addition, variables are used for the departure and the arrival airports in order to determine the optimal times for departure and for arrival. Because we do not consider flight cancellations, at least two variables can be fixed a priori for each flight: each aircraft has to take off by the end of a feasible time window and has to land, as well, within a feasible time window, which is determined by the time of departure. '''The Objective Function: The proposed model minimizes a function that is a combination of the costs of airborne delay (AH) and ground-holding delay (GH). The objective function should possess the following two desirable properties 1. Airborne delay should be more costly per unit of time than ground delay; 2. Delays to flights should be assigned “fairly.” The use of total delay has the additional advantage of overcoming the following complication: if airborne delay costs and ground delay costs are accounted for separately, as is the case in most of the models available in the existing literature, then there is no distinction between a solution that delays only one flight by assigning to that flight both one unit of airborne holding delay and one unit of ground delay, and another solution that delays two flights by assigning one unit of ground delay to one flight and one unit of airborne holding delay to the other. By contrast, if total delay is used, the model will favor the latter alternative. Summarizing, the objective function is composed of two terms: a first term that takes into account the cost of the total delay assigned to a flight and a second term that accounts for the cost reduction obtained when a part of the total delay is taken on the ground, before takeoff. The Constraints: The model’s constraints set is as follows: The first three sets of constraints take into account the capacities of the various elements of the system. Constraints (1) Ensure that the number of flights that may take off from airport k ''at time ''t ''will not exceed the departure capacity of airport ''k ''at time ''t. Likewise, Constraints(2) Ensure that the number of flights that may arrive at airport k'' at time ''t ''will not exceed the arrival capacity of airport ''k ''at time ''t. Finally, Constraints(3) Ensure that the total number of flights that may feasibly be in Sector j ''at time ''t ''will not exceed the capacity of Sector ''j ''at time ''t. The expression on the left-hand side of (3) gives the number of flights that are in Sector j ''at time ''t. Moreover, Constraints (5) and (6)'' state that a flight must arrive at one of the subsequent sectors by the latest time period at which it is allowed to reach these sectors. Constraints (7) represent connectivity between flights. They handle the cases in which a flight is continued. Constraints (8) guarantee that the total flight time does not exceed the maximum acceptable duration of the flight. Finally, Constraints (9)ensure connectivity in time. '''Computational Experience:' In this section, we present the computational experience with the mathematical model, including the valid inequalities. We consider randomly generated problem instances whose dimension is comparable to the largest-size cases that can be encountered in practice. In particular, we consider two sets of instances. The first set is analogous to the ATFM problem at a regional level, e.g., the airspace and set of airports on the East Coast or in the Midwest region of the United States. The second set consists of larger instances and is more representative of problems of national scope in the United States or near-continental scope in Europe. The size of each instance depends on the time horizon specified, the number of discrete time periods, the number of sectors, and airports considered and the size of demand at each airport. By changing one or all of the above parameters, we generate instances of different sizes. In the experimental setup, the airspace is subdivided into sectors of equal dimensions that form a grid. The rectangular shape of sectors does not detract from the model’s generality because the model can accommodate sectors of arbitrary shape. We also assume that the minimum amount of time needed to traverse a sector is the same for all the flights and for all the sectors. For each flight, the maximum acceptable flight duration has been set equal to the minimum origin destination flight time plus six time units. In order to generate instances that are consistent with hub and- spoke operations, we classify airports as either hubs or regional airports. Regional airports do not have direct connections between them but are connected through the hubs. When the capacity is 40% of the nominal value, the reduction in assigned ground and airborne holding delay is more than 15%: the amount of ground delay assigned by the model drops from 699 time units without rerouting to 600 when rerouting is an option (scale on the right-hand side of the diagram). There is also a reduction of the airborne holding delay, which drops from 132 time units to 114 (scale on the left hand side of the diagram). In the most congested case, with capacity equal to 10% of its nominal value, the amount of ground delay assigned by the model drops from 3,096 time units without rerouting to 2,640 when the rerouting option in considered. This reduction of ground delay is achieved at a cost of rerouting flights on longer flights paths, thus entailing a larger amount of airborne holding delay assigned by the model. As described in the fifth column of above table, these benefits are achieved by means of only a small number of rerouting interventions. Indeed, even in the most congested case, the number of rerouted flights is 399, corresponding to only 6.1% of the total number of flights Note also that even under good weather conditions, a large number of flights are rerouted, due to the fact that there are some o-d ''pairs with multiple routes of shortest length. More specifically, for the most congested instance, only 58 flights reroute onto longer routes. 'Fresno Yosemite International Airport' NorCal TRACON is an air traffic control facility that provides safety alerts, separation, and sequencing of air traffic arriving, departing, and transiting the airspace and airports in Northern California. NCT controls airspace over 19000 square miles. It covers the major airports in the region such as San Francisco International Airport, San Jose International Airport etc. Fresno Yosemite International Airport is one of the airports supervised by NorCAL TRACON. This airport has two runways of 8000 feet length and were built in 1953. At Tower, the supervising staff works on giving the clearance delivery. This is done with the help of transponder codes. These codes are a set of alphabets arranged in terms of points in the air and on the runway to give pilot the set of instruction about the take-off, cruising and landing. This by-default re-routes the plane as well.Generally in air two aircrafts are separated by a distance of 1000 feet vertically and 3 miles horizontally. The image shown below is the image of the TRACON screen which shows the two runways of Fresno Yosemite International Airport, nearby hospitals, cities and some local airports which might be used in case of emergency. The green dots in the image are the aircrafts flying through the region covered by the Tower/ TRACON. The Tower has different interfaces such as National Airspace System (NAS), Weather Screen (hourly updates about the weather and the altitude) and Lighting Panel or Airfield lighting Control. '''Conclusion' Hence, this new optimization model for the Air Traffic Flow Management problem makes two significant contributions. It considers a broad range of ATFM intervention options that in addition to ground and airborne delay also include speed control (through adjustments in the time spent in each sector) and, most important, rerouting. Thus, the model addresses all phases of a flight, optimizing for each flight the time of takeoff, the route, the time spent in each enroute sector, and the time of arrival, taking into account the capacity of all the elements constituting the airspace system. A key feature of the model is that decisions concerning rerouting are made efficiently using a very compact formulation that does not require any additional decision variables but only introduces new constraints that implement local routing conditions. Three classes of valid inequalities were also incorporated into the model for the purpose of strengthening the polyhedral structure of the underlying relaxation. 'References' 1. Dimitris Bertsimas, Guglielmo Lulli, and Amadeo Odoni, The ATFM Proble: An integer Optimization Approach, IPCO 2008,LNCS 5035,pp. 34-46, Springer-Verlag Berlin Heidelberg 2. Daniel B. Work and Alexandre M. Bayen, Convex Formulations of Air Traffic Flow Optimization Problems, Vol 96 No.12, Dec 2008 IEEE 3. Heinz Ezrberger, Design Principles and Algorithms for Automated Air Traffic Management, NASA AMES Research Center, CA, USA,1995